Funkcija se originalno izračunava kao: $\phi(n) = n \cdot (1 - 1/p_1)\cdot(1 - 1/p_2)\cdot ... \cdot(1 - 1/p_k)$, gde su $p_1, p_2,..., p_k$ prosti činioci broja $n$,
ali se zbog potreba celobrojnog deljenja može zapisati kao: $\phi(n) = \frac{n}{p_1 \cdot p_2 \cdot ... \cdot p_k} \cdot (p_1 - 1)\cdot(p_2 - 1)\cdot ... \cdot(p_k - 1)$
# Pomocna funkcija koja faktorise broj
def factorize(n):
if n <= 3:
return [n]
factors = []
while n % 2 == 0:
factors.append(2)
n = n // 2
i = 3
while n > 1:
if n % i == 0:
factors.append(i)
n = n // i
else:
i = i + 2
return factors
def phi(n):
primes = set(factorize(n))
res = 1
for prime in primes:
n = n // prime
res = res * (prime - 1)
return n * res
print(f'phi(7) = {phi(7)}')
print(f'phi(144) = {phi(144)}')
print(f'phi(25) = {phi(25)}')
print(f'phi(2) = {phi(2)}')
print(f'phi(2) = {phi(10)}')